﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Quick_Sort
{
    public class QuickSort
    {

        int[] arr;
        public int[] IntArray { get { return arr; } }
        public int limit;

        public QuickSort(int[] UnSortedArray, int p_limit)
        {
            arr = UnSortedArray;
            limit = p_limit;
        }

        public void SequentialSort()
        {
            seqSort(arr, 0, arr.Length - 1);
        }

        public void ParallelSort()
        {
            parSort(arr, 0, arr.Length - 1, 0);
        }

        private void seqSort(int[] list, int start, int end)
        {
            if ((end - start) < 9)
            {
                /*if(list[start]>list[end])
                {
                    int tmp = list[start];
                    list[start] = list[end];
                    list[end] = tmp;
                }*/
                InsertionSort(list, start, end + 1);
            }
            else
            {
                 
                int part = Partition(list, start, end);
                seqSort(list, start, part);
                seqSort(list, part + 1, end);
            }
        }

        private void InsertionSort(int[] list, int start, int end)
        {
            for (int x = start + 1; x < end; x++)
            {
                int val = list[x];
                int j = x - 1;
                while (j >= 0 && val < list[j])
                {
                    list[j + 1] = list[j];
                    j--;
                }
                list[j + 1] = val;
            }
        }

        private int Partition(int[] a, int p, int r)
        {
            int pdex= ((p/2)+(r/2));
            
            int x = a[pdex];
            
            int i = p-1;
            int j = r;
            while (true)
            {
                do j = j- 1; while (a[j] > x);
                do i =i + 1; while (a[i] < x);

                if (i < j)
                {
                    int tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;
                }
                else
                    return j;
            }
        }
        /*private int Partition(int[] list, int leftIndex, int rightIndex)
        {
            int pivot = list[leftIndex];
            int left = leftIndex;
            int right = rightIndex;

            while (left < right)
            {
                if (list[left] < pivot)
                {
                    left++;

                }
                if (list[right] > pivot)
                {
                    right--;

                }
                int tmp = list[left];
                list[left] = list[right];
                list[right] = tmp;
                left++;
            }
            return left;
        }*/


        private void parSort(int[] list, int start, int end, int level)
        {

            if ((end - start) <= 9)
            {
                InsertionSort(list, start, end + 1);
            }
            else
            {
                
               int part = Partition(list, start, end);

                if (level < limit)
                {
                    var t1 = Task.Factory.StartNew(() => parSort(list, start, part - 1, level + 1));
                    var t2 = Task.Factory.StartNew(() => parSort(list, part + 1, end, level + 1));

                    Task.WaitAll(t1, t2);
                }
                else
                {
                    seqSort(list, start, part);
                    seqSort(list, part + 1, end);
                }

            }

        }


    }
}
